package com.lsa.letcode.the33.searchInRotatedArrNoDupl;

public class Solution {
    /**
     * 6 7 1 2 3 4 5
     * 
     * @param nums
     * @param t target
     * @return
     */
    public int search(int[] nums, int t) {
    	if (nums.length == 0) {
    		return -1;
    	}
    	else if (nums.length == 1) {
    		return nums[0] == t? 0 : -1;
    	}
        int pivotIdx = pivot(nums);
        if (pivotIdx < 0) {
        	return binarySearch(nums, 0 , nums.length - 1, t);
        }
        int elIdx = binarySearch(nums, 0 , pivotIdx, t);
        if (elIdx > - 1) {
        	return elIdx;
        }
        else {
        	return binarySearch(nums, pivotIdx +1 , nums.length - 1, t);
        }
    }
    
    private int pivot(int[] nums) {
    	int low = 0;
    	int len = nums.length;
		int high = len - 1;
    	while(low <= high) {
			int mid = (low + high) >> 1;
    		if (mid == 0) {
    			if (nums[0] > nums[1]) {
    				return 0;
    			}
    			else {
    				low = mid + 1;
    			}
    		}
    		else if (mid == len - 1) {
    			if (nums[len - 2] > nums[len - 1]) {
    				return len - 2;
    			}
    			else {
    				high = mid  - 1;
    			}
    		}
    		else {
    			if (nums[mid] > nums[mid + 1]) {
    				return mid;
    			}
    			else if (nums[mid - 1] > nums[mid]) {
    				return mid - 1;
    			}
    			else if (nums[mid] > nums[len - 1]){
    				low = mid + 1;
    			}
    			else {
    				high = mid - 1;
    			}
    		}
		}
		return -1;
	}

	private int binarySearch(int[] nums, int low, int high, int t) {
		while(low <= high) {
			int mid = (low + high) >> 1;
			if (nums[mid] < t) {
				low = mid + 1;
			}
			else if (nums[mid] > t){
				high = mid - 1;
			}
			else {
				return mid;
			}
		}
		return -1;
	}
}